
import time

def calcTime(func):
        '''
        函数修饰器, 用来计算求出最小生命值所需要的时间
        最终返回一个 list [temp, time_sum]
        '''
        def warpper (*args, **kwds):
            time_start = time.perf_counter()
            temp = func(*args, **kwds)
            time_end = time.perf_counter()
            time_sum = time_end - time_start
            return [temp, time_sum*1000]
        return warpper


class MinHP:
    def __init__(self , dungeon):
        self.map = dungeon                  #地下城地图的赋值
        self.rows = len(self.map)           #地下城地图的行数
        self.columns = len(self.map[0])     #地下城地图的列数

    @calcTime
    def calculateMinimumHP(self):
        n, m = self.rows, self.columns

        #dp[i][j] 表示从坐标 (i,j) 到终点所需的最小初始值
        #先为dp[][] 都给赋上极大的值
        BIG = 10 ** 9
        dp = [[BIG] * (m + 1) for _ in range(n + 1)]

        # dp[n−1][m−1] 转移需要用到的 dp[n−1][m]和dp[n][m−1] 均为无效值，给这两个值赋值为 1
        dp[n][m - 1] = dp[n - 1][m] = 1

        #从右下向左上进行迭代
        for i in range(n - 1, -1, -1):
            for j in range(m - 1, -1, -1):
                minn = min(dp[i + 1][j], dp[i][j + 1])   #由于每次只能向下或者向右 ，从两种选择中找到较小的
                dp[i][j] = max(minn - self.map[i][j], 1) #状态转移方程

        return dp[0][0]

if __name__ == "__main__":
    testlist = [[-2,-3,3] , [-5,-10,1] , [10,30,-5]]
    test0 = MinHP(testlist)
    print(test0.calculateMinimumHP())
